import functools


class Solution(object):
    def optimalDivision(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """

        @functools.cache
        def search_max(i, j):
            if i == j:
                return nums[i], str(nums[i])
            if j - i == 1:
                return nums[i] / nums[j], str(nums[i]) + '/' + str(nums[j])
            max_val = 0
            max_s = ''
            for k in range(i, j):
                left_val, left_s = search_max(i, k)
                right_val, right_s = search_min(k + 1, j)
                if left_val / right_val > max_val:
                    max_val = left_val / right_val
                    if k == j - 1:
                        max_s = left_s + '/' + right_s
                    else:
                        max_s = left_s + '/(' + right_s + ')'
            return max_val, max_s

        @functools.cache
        def search_min(i, j):
            if i == j:
                return nums[i], str(nums[i])
            if j - i == 1:
                return nums[i] / nums[j], str(nums[i]) + '/' + str(nums[j])
            min_val = float('inf')
            min_s = ''
            for k in range(i, j):
                left_val, left_s = search_min(i, k)
                right_val, right_s = search_max(k + 1, j)
                if left_val / right_val < min_val:
                    min_val = left_val / right_val
                    if k == j - 1:
                        min_s = left_s + '/' + right_s
                    else:
                        min_s = left_s + '/(' + right_s + ')'
            return min_val, min_s

        return search_max(0, len(nums) - 1)[1]


data = Solution()
nums = [1000, 100, 10, 2]
print(data.optimalDivision(nums))
